package 二叉树练习题;

public class B如何把一个有序的整数数组放到二叉树中 {


    public static BiTNode arraytotree(int[] arr, int start, int end) {

        BiTNode root = null;
        if (end >= start) {
            root = new BiTNode();
            int mid = (start + end + 1) / 2;
            //树的根节点为数组中间的元素
            root.data = arr[mid];
            //递归的用右半部分数组构造root的右子树
            root.lchild = arraytotree(arr, start, mid - 1);
            //递归的用右半部分数组构造root的右子树
            root.rchild = arraytotree(arr, mid + 1, end);
        } else {
            root = null;
        }
        return root;
    }

    public static void printTreeMidOrder(BiTNode root) {
        if (root == null) {
            return;
        }
        if (root.lchild != null) {
            printTreeMidOrder(root.lchild);
        }
        //遍历root节点
        System.out.print(root.data + " ");
        //遍历root节点的右子树
        if (root.rchild != null) {
            printTreeMidOrder(root.rchild);
        }
    }

    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println("数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        BiTNode root = arraytotree(arr, 0, arr.length - 1);
        System.out.println("转换成树的中序遍历为：");
        printTreeMidOrder(root);
        System.out.println();
    }
}
